#include <iostream>
#include <cmath>
#include <cstdio>
#include <string>
#include <cstdlib>
#include <fstream>
#include <cstring>
#include <algorithm>
#include <ctime>
#include <map>

using namespace std;
typedef unsigned char BYTE;
typedef unsigned short WORD;
typedef unsigned long DWORD;
typedef long LONG;
#define WIDTHBYTES(bits) (((bits) + 31) / 32 * 4)

#pragma pack(1)
//调色板与颜色表
typedef struct RGBQUAD
{
    BYTE rgbBlue;
    BYTE rgbGreen;
    BYTE rgbRed;
    BYTE rgbReserved;
} BGRA;
//位图文件头，为14个字节
typedef struct tagBITMAPFILEHEADER
{
    WORD bfType;
    DWORD bfSize;     //文件大小
    WORD bfReserved1; //保留字，不考虑
    WORD bfReserved2; //保留字，同上
    DWORD bfOffBits;  //实际位图数据的偏移字节数，即前三个部分长度之和
} BmpFileHeader;
//位图信息头，为40个字节
typedef struct tagBITMAPINFOHEADER
{
    DWORD biSize;         //指定此结构体的长度，为40
    LONG biWidth;         //位图宽
    LONG biHeight;        //位图高
    WORD biPlanes;        //平面数，为1
    WORD biBitCount;      //采用颜色位数，可以是1，2，4，8，16，24，新的可以是32
    DWORD biCompression;  //压缩方式，可以是0，1，2，其中0表示不压缩
    DWORD biSizeImage;    //实际位图数据占用的字节数
    LONG biXPelsPerMeter; //X方向分辨率
    LONG biYPelsPerMeter; //Y方向分辨率
    DWORD biClrUsed;      //使用的颜色数，如果为0，则表示默认值(2^颜色位数)
    DWORD biClrImportant; //重要颜色数，如果为0，则表示所有颜色都是重要的
} BmpInfoHeader;

//bmp图像类
class BmpImage
{
private:
    BmpFileHeader Fheader; //图像文件头
    BmpInfoHeader Iheader; //图像信息头
    RGBQUAD **palette;     //调色板
    BGRA **bgra;           //24/32位用的rgba颜色
    long width;            //宽度
    long height;           //高度
    WORD depth;            //深度
    BYTE *idata;           //存储图像的数据
    int l_width;           //补齐宽度
    long grayhist[256];    //灰度直方图数组
public:
    BYTE rgbarray[4]; //暂时存储某一个像素的rgba颜色表的四个成员，方便运算,并且需要将其公有化方便调用
    //将某个像素的rgba颜色表放在一个数组中，方便运算
    void addArray(long i, long j)
    {
        memset(rgbarray, 0, 4);
        rgbarray[0] = bgra[i][j].rgbRed;
        rgbarray[1] = bgra[i][j].rgbGreen;
        rgbarray[2] = bgra[i][j].rgbBlue;
        rgbarray[3] = bgra[i][j].rgbReserved;
    }
    //处理某个像素在图像运算之后的溢出问题
    void clearOverflow()
    {
        int i = 0;
        for (i = 0; i < 4; ++i)
        {
            if (rgbarray[i] > 255)
                rgbarray[i] = 255;
            if (rgbarray[i] < 0)
                rgbarray[i] = 0;
        }
    }
    //将某个像素的颜色数组释放到颜色表中，用来更改成运算后的结果
    void popArray(long i, long j)
    {
        bgra[i][j].rgbRed = rgbarray[0];
        bgra[i][j].rgbGreen = rgbarray[1];
        bgra[i][j].rgbBlue = rgbarray[2];
        bgra[i][j].rgbReserved = rgbarray[3];
        memset(rgbarray, 0, 4);
    }
    explicit BmpImage(char *filename) //构造函数
    {
        if (!readBmp(filename))
        {
            printf("Failed to create the bmpimage %s\n", filename);
        }
        else
        {
            printf("Succeed to create the bmpimage %s\n", filename);
        }
    }
    bool readBmp(char *filename)
    {
        ifstream infile(filename, ios::binary);
        // 检查文件是否打开
        if (!infile.is_open())
        {
            printf("Failed to open file %s\n", filename);
            return false;
        }
        // 读取BmpFileHeader
        infile.read((char *)(&Fheader), sizeof(BmpFileHeader));
        // 判断是否是bmp图像
        if (Fheader.bfType != 0x4d42) // 0x4d42 = 'BM'
        {
            printf("File %s is not bmp file\n", filename);
            return false;
        }
        // 读取BmpInfoHeader
        infile.read((char *)(&Iheader), sizeof(BmpInfoHeader));
        // 判断是否有调色板，如果有就读取调色板数据
        if (Fheader.bfOffBits == 54)
        { //说明文件头和信息头的大小就是偏移量，没有调色板
            palette = nullptr;
        }
        else
        {
            // 读取调色板数据,24/32位颜色表赋空值
            infile.read((char *)(palette), Fheader.bfOffBits - 54);
            bgra = nullptr;
        }
        // 给属性赋值
        width = Iheader.biWidth;
        height = Iheader.biHeight;
        depth = Iheader.biBitCount;
        memset(rgbarray, 0, 4);
        // 读取图像数据
        // 申请内存空间并初始化为0
        l_width = WIDTHBYTES(width * depth);
        long datasize = height * l_width;
        idata = new BYTE[datasize];
        memset(idata, 0, datasize);
        // 读取图像数据到内存
        infile.read((char *)idata, datasize);
        //图像是24或32位时，运行rgba()函数，将像素的rgba值保存到数组bgra中
        if (depth == 32 || depth == 24)
        {
            rgba();
        }
        infile.close();
        return true;
    }
    //如果图像是32/24位，求图像RGBA值
    bool rgba()
    {
        if (depth != 24 && depth != 32)
        {
            printf("The image is not 24bit or 32bit\n");
            return false;
        }
        //补齐宽度
        l_width = WIDTHBYTES(width * depth);
        bgra = NULL;
        long i, j;
        bgra = new BGRA *[height];
        for (i = 0; i < height; i++)
            bgra[i] = new BGRA[width];
        int k;
        int index = 0;
        if (depth == 32)
            for (i = 0; i < height; i++)
            {
                int k0 = (height - i - 1) * l_width;
                for (j = 0; j < width; j++)
                {
                    k = k0 + (j * 4);
                    bgra[i][j].rgbRed = idata[k + 2];
                    bgra[i][j].rgbGreen = idata[k + 1];
                    bgra[i][j].rgbBlue = idata[k];
                    bgra[i][j].rgbReserved = idata[k + 3];
                }
            }
        if (depth == 24)
            for (i = 0; i < height; i++)
            {
                int k0 = (height - i - 1) * l_width;
                for (j = 0; j < width; j++)
                {
                    k = k0 + (j * 3);
                    bgra[i][j].rgbRed = idata[k + 2];
                    bgra[i][j].rgbGreen = idata[k + 1];
                    bgra[i][j].rgbBlue = idata[k];
                    bgra[i][j].rgbReserved = 0;
                }
            }
        return true;
    }
    //显示bmp文件头属性
    void showBmpFileHead()
    {
        printf("BmpFileHead：\n");
        printf("Filetype:%x\n", Fheader.bfType);
        printf("Filesize:%d\n", Fheader.bfSize);
        printf("Reserved1:%d\n", Fheader.bfReserved1);
        printf("Reserved2:%d\n", Fheader.bfReserved2);
        printf("Offbits:%d\n", Fheader.bfOffBits);
    }
    //显示bmp信息头属性
    void showBmpInfoHead()
    {
        printf("BmpInfoHead：\n");
        printf("Width:%d\n", Iheader.biWidth);
        printf("Height:%d\n", Iheader.biHeight);
        printf("Planes:%d\n", Iheader.biPlanes);
        printf("Bitcount:%d\n", Iheader.biBitCount);
        printf("Compression:%d\n", Iheader.biCompression);
        printf("Sizeimage:%d\n", Iheader.biSizeImage);
        printf("X-pixels per meter:%d\n", Iheader.biXPelsPerMeter);
        printf("Y-pixels per meter:%d\n", Iheader.biYPelsPerMeter);
        printf("Colors used:%d\n", Iheader.biClrUsed);
        printf("Important colors used:%d\n", Iheader.biClrImportant);
    }
    //将图像32位保存到指定文件
    bool saveBmp(char *filename)
    {
        long i, j;
        ofstream outfile(filename, ios::binary);
        Iheader.biBitCount = 32;
        outfile.write((char *)&Fheader, sizeof(Fheader));
        outfile.write((char *)&Iheader, sizeof(Iheader));
        int lwidth = WIDTHBYTES(width * 32) - width * 4; //计算为确保位图数据区的实际宽度为32字节的整数倍需添加的0字节个数
        for (i = 0; i < height; i++)
        {
            for (j = 0; j < width; j++)
            {
                outfile.write((char *)(&bgra[height - i - 1][j]), 4);
            }
            BYTE tmp = 0;
            for (j = 0; j < lwidth; j++)
                outfile << tmp;
        }
        cout << "Succeed to save bmpfile on " << filename << endl;
        outfile.close();
        return true;
    }
    //rgb图像转灰度图像
    void convertRGB2Gray()
    {
        double gray;
        for (long i = 0; i < height; i++)
        {
            for (long j = 0; j < width; j++)
            {
                gray = 0.299 * bgra[i][j].rgbRed + 0.587 * bgra[i][j].rgbGreen + 0.114 * bgra[i][j].rgbBlue;
                bgra[i][j].rgbRed = (BYTE)gray;
                bgra[i][j].rgbGreen = (BYTE)gray;
                bgra[i][j].rgbBlue = (BYTE)gray;
            }
        }
        printf("Succeed to convert rgb to gray\n");
    }
    //生成灰度直方图
    void saveHist()
    {
        // 生成灰度直方图数组
        memset(grayhist, 0L, sizeof(grayhist));
        convertRGB2Gray();
        int i, j, id;
        for (i = 0; i < height; i++)
        {
            for (j = 0; j < width; j++)
            {
                id = bgra[i][j].rgbBlue;
                grayhist[id] = grayhist[id] + 1L;
            }
        }
    }
    //用随机数添加椒盐噪声
    void addSalt(int n = 10)
    {
        srand(int(time(0)));
        long i, j;
        int k;
        int x;
        for (k = 0; k < n; ++k)
        {
            i = rand() % height;
            j = rand() % width;
            addArray(i, j);
            for (x = 0; x < 4; ++x)
            {
                rgbarray[x] = 0;
            }
            popArray(i, j);
        }
        char str[] = "salted.bmp";
        printf("Succeed to add salt on %s\n", str);
        saveBmp(str);
        rgba();
    }

    //-----------------------第七章 图像分割-----------
    //二值化,参数是阈值
    void binarize(double th)
    {
        //转灰度
        convertRGB2Gray();
        //二值化，灰度值低于阈值的置0否则置255
        long i, j;
        for (i = 0; i < height; ++i)
        {
            for (j = 0; j < width; ++j)
            {
                addArray(i, j);
                for (int k = 0; k < 4; ++k)
                {
                    rgbarray[k] = (BYTE)(rgbarray[k] < th ? 0 : 255);
                }
                popArray(i, j);
            }
        }
        printf("Succeed to binarize\n");
    }
    //p参数分割法，默认0.4
    void ptileSplit(double p = 0.4)
    {
        long total = width * height;
        long psum = 0;
        double th = 0.0;
        //生成直方图
        saveHist();
        int i = 0;
        for (i; i < 256; ++i)
        {
            psum += grayhist[i];
            if (psum >= p * total)
            {
                th = i;
                break;
            }
        }
        //以生成的阈值二值化
        binarize(th);
        char src[] = "p-tile.bmp";
        printf("Succeed to p-tilesplit on %s and threshold is %d \n", src, th);
        saveBmp(src);
        rgba();
    }
    //均匀度量法，迭代过程中的阈值
    double thofIteration(double tth)
    {
        long total = width * height;
        int th = (int)tth;
        long *c1, *c2;
        c1 = new long[th];
        c2 = new long[256 - th];
        int i;
        for (i = 0; i < 256; ++i)
        {
            if (i < th)
            {
                c1[i] = grayhist[i];
            }
            else
            {
                c2[i - th] = grayhist[i];
            }
        }
        double m1 = 0.0, m2 = 0.0;
        long sum1 = 0, sum2 = 0;
        for (i = 0; i < th; ++i)
        {
            sum1 += c1[i];
            m1 += (double)c1[i] * i;
        }
        m1 = m1 / sum1;
        for (i = 0; i < 256 - th; ++i)
        {
            sum2 += c2[i];
            m2 += (double)c2[i] * (i + th);
        }
        m2 = m2 / sum2;
        return (m1 + m2) / 2;
    }
    //均匀度量法，用迭代法生成阈值,参数是初始阈值，默认是128
    void uniformSplit(double th1 = 128.0)
    {
        int th;
        saveHist();
        double dt = 0.001;
        double th2 = thofIteration(th1);
        //迭代法生成阈值
        while (fabs(th2 - th1) > dt)
        {
            th1 = th2;
            th2 = thofIteration(th1);
        }
        th = (int)th2;
        //以生成的阈值二值化
        binarize(th);
        char src[] = "uniform.bmp";
        printf("Succeed to uniformsplit on %s and threshold is %d \n", src, th);
        saveBmp(src);
        rgba();
    }
    //聚类法的迭代函数
    pair<double, int> clusterIter(int th)
    {
        long total = 0;
        long sum1 = 0, sum2 = 0;
        long *c1, *c2;
        c1 = new long[th];
        c2 = new long[256 - th];
        int i;
        for (i = 0; i < 256; ++i)
        {
            if (i < th)
            {
                c1[i] = grayhist[i];
                sum1 += c1[i];
            }
            else
            {
                c2[i - th] = grayhist[i];
                sum2 += c2[i - th];
            }
            total += grayhist[i];
        }
        double m1 = 0.0, m2 = 0.0;
        double var1 = 0.0, var2 = 0.0;
        double p1 = 0.0, p2 = 0.0;
        for (i = 0; i < th; ++i)
        {
            m1 += (double)c1[i] * i;
        }
        m1 = m1 / sum1;
        p1 = (double)sum1 / total;
        for (i = 0; i < 256 - th; ++i)
        {
            m2 += (double)c2[i] * (i + th);
        }
        m2 = m2 / sum2;
        p2 = (double)sum2 / total;
        for (i = 0; i < th; ++i)
        {
            var1 += (m1 - i) * (m1 - i);
        }
        for (i = 0; i < 256 - th; ++i)
        {
            var2 += (m2 - i - th) * (m2 - i - th);
        }
        double res1 = var1 * p1 + var2 * p2;
        int tth = (m1 + m2) / 2;
        return pair<double, int>(res1, tth);
    }
    //聚类算法,参数是初始阈值，默认128
    void clusterSplit(int tth = 128)
    {
        int th;
        saveHist();
        int i;
        pair<double, int> it0, it1;
        it0 = clusterIter(tth);
        it1 = clusterIter(it0.second);
        while (it0.first > it1.first)
        {
            it0.second = it1.second;
            it0.first = it1.first;
            it1 = clusterIter(it0.second);
        }
        th = it0.second;
        //以生成的阈值二值化
        binarize(th);
        char src[] = "cluster.bmp";
        printf("Succeed to clustersplit on %s and threshold is %d \n", src, th);
        saveBmp(src);
        rgba();
    }
    //全局阈值自动分割,参数是阈值，默认128
    void autoSplit(int th = 128)
    {
        saveHist();
        //以设定阈值二值化
        binarize(th);
        char src[] = "auto.bmp";
        printf("Succeed to autosplit on %s and threshold is %d \n", src, th);
        saveBmp(src);
        rgba();
    }
};